<head>
    <meta charset="UTF-8">
<title>算法训练 SPFA</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
SPFA<br />
【输入格式】<br />
第一行输入n,m；第二行输入begin,end</p>
<p>&nbsp;</p>
<p>接下来m行输入x,y,z;</p>
<p>&nbsp;</p>
<p>n表示点数，m表示边数，begin表示起始点，end表示目标点，x、y表示连同连点z表示权值<br />
【输出格式】<br />
输出begin到end的最短路<br />
【样例输入】</p>
<div>7 12</div>
<div>1 7</div>
<div>1 7 10</div>
<div>1 2 1</div>
<div>1 3 2</div>
<div>2 7 8</div>
<div>2 3 1</div>
<div>2 4 4</div>
<div>2 5 1</div>
<div>2 6 10</div>
<div>3 4 3</div>
<div>5 6 1</div>
<div>5 4 7</div>
<div>6 7 1</div>
<p>【样例输出】<br />
4<br />
【数据规模和约定】<br />
n,m&lt;10^6</p>